public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        String s = "aa";
        String p = "a*a*a*a*a*";
        System.out.println(test.isMatch(s, p));
    }

    public boolean isMatch(String s, String p) {
        /**0
         * 正则表达式匹配
         *  状态表示：
         *      dp[i][j]表示s字符串[0,i]范围子字符串 与 p字符串[0,j]范围子字符串是否能够完全匹配
         *  状态转移方程：
         *
         *  初始化：
         *      使用虚拟位置法，引入空串概念
         *  填表顺序：
         *      从上到下，从左到右
         * */
        // 1 预处理
        int m = s.length();
        int n = p.length();
        // 2 创建dp表
        boolean[][] dp = new boolean[m+1][n+1];
        // 3 初始化
        dp[0][0] = true;
        for(int k = 2; k <= n; k+=2) {
            if(p.charAt(k-1) == '*') {
                dp[0][k-1] = dp[0][k] = true;
            } else{
                break;
            }
        }
        // 4 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(p.charAt(j-1) == '.') {
                    dp[i][j] = dp[i-1][j-1];
                } else if(p.charAt(j-1) == '*') {
                    if(p.charAt(j-2) == '.') {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    } else {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j] && s.charAt(i-1) == p.charAt(j-2);
                    }
                } else {
                    dp[i][j] = s.charAt(i-1) == p.charAt(j-1) && dp[i-1][j-1];
                }
            }
        }
        // 5 返回值
        return dp[m][n];
    }
}
